home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 4 / Amiga Tools 4.iso / grafix / tools / jpeg / jpeg-6a / jcphuff.c < prev    next >
C/C++ Source or Header  |  1996-01-06  |  25KB  |  830 lines
  1. /*
  2.  * jcphuff.c
  3.  *
  4.  * Copyright (C) 1995-1996, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy encoding routines for progressive JPEG.
  9.  *
  10.  * We do not support output suspension in this module, since the library
  11.  * currently does not allow multiple-scan files to be written with output
  12.  * suspension.
  13.  */
  14.  
  15. #define JPEG_INTERNALS
  16. #include "jinclude.h"
  17. #include "jpeglib.h"
  18. #include "jchuff.h"        /* Declarations shared with jchuff.c */
  19.  
  20. #ifdef C_PROGRESSIVE_SUPPORTED
  21.  
  22. /* Expanded entropy encoder object for progressive Huffman encoding. */
  23.  
  24. typedef struct {
  25.   struct jpeg_entropy_encoder pub; /* public fields */
  26.  
  27.   /* Mode flag: TRUE for optimization, FALSE for actual data output */
  28.   boolean gather_statistics;
  29.  
  30.   /* Bit-level coding status.
  31.    * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
  32.    */
  33.   JOCTET * next_output_byte;    /* => next byte to write in buffer */
  34.   size_t free_in_buffer;    /* # of byte spaces remaining in buffer */
  35.   INT32 put_buffer;        /* current bit-accumulation buffer */
  36.   int put_bits;            /* # of bits now in it */
  37.   j_compress_ptr cinfo;        /* link to cinfo (needed for dump_buffer) */
  38.  
  39.   /* Coding status for DC components */
  40.   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  41.  
  42.   /* Coding status for AC components */
  43.   int ac_tbl_no;        /* the table number of the single component */
  44.   unsigned int EOBRUN;        /* run length of EOBs */
  45.   unsigned int BE;        /* # of buffered correction bits before MCU */
  46.   char * bit_buffer;        /* buffer for correction bits (1 per char) */
  47.   /* packing correction bits tightly would save some space but cost time... */
  48.  
  49.   unsigned int restarts_to_go;    /* MCUs left in this restart interval */
  50.   int next_restart_num;        /* next restart number to write (0-7) */
  51.  
  52.   /* Pointers to derived tables (these workspaces have image lifespan).
  53.    * Since any one scan codes only DC or only AC, we only need one set
  54.    * of tables, not one for DC and one for AC.
  55.    */
  56.   c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
  57.  
  58.   /* Statistics tables for optimization; again, one set is enough */
  59.   long * count_ptrs[NUM_HUFF_TBLS];
  60. } phuff_entropy_encoder;
  61.  
  62. typedef phuff_entropy_encoder * phuff_entropy_ptr;
  63.  
  64. /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
  65.  * buffer can hold.  Larger sizes may slightly improve compression, but
  66.  * 1000 is already well into the realm of overkill.
  67.  * The minimum safe size is 64 bits.
  68.  */
  69.  
  70. #define MAX_CORR_BITS  1000    /* Max # of correction bits I can buffer */
  71.  
  72. /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
  73.  * We assume that int right shift is unsigned if INT32 right shift is,
  74.  * which should be safe.
  75.  */
  76.  
  77. #ifdef RIGHT_SHIFT_IS_UNSIGNED
  78. #define ISHIFT_TEMPS    int ishift_temp;
  79. #define IRIGHT_SHIFT(x,shft)  \
  80.     ((ishift_temp = (x)) < 0 ? \
  81.      (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
  82.      (ishift_temp >> (shft)))
  83. #else
  84. #define ISHIFT_TEMPS
  85. #define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
  86. #endif
  87.  
  88. /* Forward declarations */
  89. METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo,
  90.                         JBLOCKROW *MCU_data));
  91. METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo,
  92.                         JBLOCKROW *MCU_data));
  93. METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo,
  94.                          JBLOCKROW *MCU_data));
  95. METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo,
  96.                          JBLOCKROW *MCU_data));
  97. METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo));
  98. METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo));
  99.  
  100.  
  101. /*
  102.  * Initialize for a Huffman-compressed scan using progressive JPEG.
  103.  */
  104.  
  105. METHODDEF(void)
  106. start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
  107. {  
  108.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  109.   boolean is_DC_band;
  110.   int ci, tbl;
  111.   jpeg_component_info * compptr;
  112.  
  113.   entropy->cinfo = cinfo;
  114.   entropy->gather_statistics = gather_statistics;
  115.  
  116.   is_DC_band = (cinfo->Ss == 0);
  117.  
  118.   /* We assume jcmaster.c already validated the scan parameters. */
  119.  
  120.   /* Select execution routines */
  121.   if (cinfo->Ah == 0) {
  122.     if (is_DC_band)
  123.       entropy->pub.encode_mcu = encode_mcu_DC_first;
  124.     else
  125.       entropy->pub.encode_mcu = encode_mcu_AC_first;
  126.   } else {
  127.     if (is_DC_band)
  128.       entropy->pub.encode_mcu = encode_mcu_DC_refine;
  129.     else {
  130.       entropy->pub.encode_mcu = encode_mcu_AC_refine;
  131.       /* AC refinement needs a correction bit buffer */
  132.       if (entropy->bit_buffer == NULL)
  133.     entropy->bit_buffer = (char *)
  134.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  135.                       MAX_CORR_BITS * SIZEOF(char));
  136.     }
  137.   }
  138.   if (gather_statistics)
  139.     entropy->pub.finish_pass = finish_pass_gather_phuff;
  140.   else
  141.     entropy->pub.finish_pass = finish_pass_phuff;
  142.  
  143.   /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
  144.    * for AC coefficients.
  145.    */
  146.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  147.     compptr = cinfo->cur_comp_info[ci];
  148.     /* Initialize DC predictions to 0 */
  149.     entropy->last_dc_val[ci] = 0;
  150.     /* Make sure requested tables are present */
  151.     /* (In gather mode, tables need not be allocated yet) */
  152.     if (is_DC_band) {
  153.       if (cinfo->Ah != 0)    /* DC refinement needs no table */
  154.     continue;
  155.       tbl = compptr->dc_tbl_no;
  156.       if (tbl < 0 || tbl >= NUM_HUFF_TBLS ||
  157.       (cinfo->dc_huff_tbl_ptrs[tbl] == NULL && !gather_statistics))
  158.     ERREXIT1(cinfo,JERR_NO_HUFF_TABLE, tbl);
  159.     } else {
  160.       entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
  161.       if (tbl < 0 || tbl >= NUM_HUFF_TBLS ||
  162.           (cinfo->ac_huff_tbl_ptrs[tbl] == NULL && !gather_statistics))
  163.         ERREXIT1(cinfo,JERR_NO_HUFF_TABLE, tbl);
  164.     }
  165.     if (gather_statistics) {
  166.       /* Allocate and zero the statistics tables */
  167.       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
  168.       if (entropy->count_ptrs[tbl] == NULL)
  169.     entropy->count_ptrs[tbl] = (long *)
  170.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  171.                       257 * SIZEOF(long));
  172.       MEMZERO(entropy->count_ptrs[tbl], 257 * SIZEOF(long));
  173.     } else {
  174.       /* Compute derived values for Huffman tables */
  175.       /* We may do this more than once for a table, but it's not expensive */
  176.       if (is_DC_band)
  177.         jpeg_make_c_derived_tbl(cinfo, cinfo->dc_huff_tbl_ptrs[tbl],
  178.                 & entropy->derived_tbls[tbl]);
  179.       else
  180.         jpeg_make_c_derived_tbl(cinfo, cinfo->ac_huff_tbl_ptrs[tbl],
  181.                 & entropy->derived_tbls[tbl]);
  182.     }
  183.   }
  184.  
  185.   /* Initialize AC stuff */
  186.   entropy->EOBRUN = 0;
  187.   entropy->BE = 0;
  188.  
  189.   /* Initialize bit buffer to empty */
  190.   entropy->put_buffer = 0;
  191.   entropy->put_bits = 0;
  192.  
  193.   /* Initialize restart stuff */
  194.   entropy->restarts_to_go = cinfo->restart_interval;
  195.   entropy->next_restart_num = 0;
  196. }
  197.  
  198.  
  199. /* Outputting bytes to the file.
  200.  * NB: these must be called only when actually outputting,
  201.  * that is, entropy->gather_statistics == FALSE.
  202.  */
  203.  
  204. /* Emit a byte */
  205. #define emit_byte(entropy,val)  \
  206.     { *(entropy)->next_output_byte++ = (JOCTET) (val);  \
  207.       if (--(entropy)->free_in_buffer == 0)  \
  208.         dump_buffer(entropy); }
  209.  
  210.  
  211. LOCAL(void)
  212. dump_buffer (phuff_entropy_ptr entropy)
  213. /* Empty the output buffer; we do not support suspension in this module. */
  214. {
  215.   struct jpeg_destination_mgr * dest = entropy->cinfo->dest;
  216.  
  217.   if (! (*dest->empty_output_buffer) (entropy->cinfo))
  218.     ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
  219.   /* After a successful buffer dump, must reset buffer pointers */
  220.   entropy->next_output_byte = dest->next_output_byte;
  221.   entropy->free_in_buffer = dest->free_in_buffer;
  222. }
  223.  
  224.  
  225. /* Outputting bits to the file */
  226.  
  227. /* Only the right 24 bits of put_buffer are used; the valid bits are
  228.  * left-justified in this part.  At most 16 bits can be passed to emit_bits
  229.  * in one call, and we never retain more than 7 bits in put_buffer
  230.  * between calls, so 24 bits are sufficient.
  231.  */
  232.  
  233. INLINE
  234. LOCAL(void)
  235. emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size)
  236. /* Emit some bits, unless we are in gather mode */
  237. {
  238.   /* This routine is heavily used, so it's worth coding tightly. */
  239.   register INT32 put_buffer = (INT32) code;
  240.   register int put_bits = entropy->put_bits;
  241.  
  242.   /* if size is 0, caller used an invalid Huffman table entry */
  243.   if (size == 0)
  244.     ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
  245.  
  246.   if (entropy->gather_statistics)
  247.     return;            /* do nothing if we're only getting stats */
  248.  
  249.   put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
  250.   
  251.   put_bits += size;        /* new number of bits in buffer */
  252.   
  253.   put_buffer <<= 24 - put_bits; /* align incoming bits */
  254.  
  255.   put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
  256.  
  257.   while (put_bits >= 8) {
  258.     int c = (int) ((put_buffer >> 16) & 0xFF);
  259.     
  260.     emit_byte(entropy, c);
  261.     if (c == 0xFF) {        /* need to stuff a zero byte? */
  262.       emit_byte(entropy, 0);
  263.     }
  264.     put_buffer <<= 8;
  265.     put_bits -= 8;
  266.   }
  267.  
  268.   entropy->put_buffer = put_buffer; /* update variables */
  269.   entropy->put_bits = put_bits;
  270. }
  271.  
  272.  
  273. LOCAL(void)
  274. flush_bits (phuff_entropy_ptr entropy)
  275. {
  276.   emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
  277.   entropy->put_buffer = 0;     /* and reset bit-buffer to empty */
  278.   entropy->put_bits = 0;
  279. }
  280.  
  281.  
  282. /*
  283.  * Emit (or just count) a Huffman symbol.
  284.  */
  285.  
  286. INLINE
  287. LOCAL(void)
  288. emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol)
  289. {
  290.   if (entropy->gather_statistics)
  291.     entropy->count_ptrs[tbl_no][symbol]++;
  292.   else {
  293.     c_derived_tbl * tbl = entropy->derived_tbls[tbl_no];
  294.     emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
  295.   }
  296. }
  297.  
  298.  
  299. /*
  300.  * Emit bits from a correction bit buffer.
  301.  */
  302.  
  303. LOCAL(void)
  304. emit_buffered_bits (phuff_entropy_ptr entropy, char * bufstart,
  305.             unsigned int nbits)
  306. {
  307.   if (entropy->gather_statistics)
  308.     return;            /* no real work */
  309.  
  310.   while (nbits > 0) {
  311.     emit_bits(entropy, (unsigned int) (*bufstart), 1);
  312.     bufstart++;
  313.     nbits--;
  314.   }
  315. }
  316.  
  317.  
  318. /*
  319.  * Emit any pending EOBRUN symbol.
  320.  */
  321.  
  322. LOCAL(void)
  323. emit_eobrun (phuff_entropy_ptr entropy)
  324. {
  325.   register int temp, nbits;
  326.  
  327.   if (entropy->EOBRUN > 0) {    /* if there is any pending EOBRUN */
  328.     temp = entropy->EOBRUN;
  329.     nbits = 0;
  330.     while ((temp >>= 1))
  331.       nbits++;
  332.  
  333.     emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
  334.     if (nbits)
  335.       emit_bits(entropy, entropy->EOBRUN, nbits);
  336.  
  337.     entropy->EOBRUN = 0;
  338.  
  339.     /* Emit any buffered correction bits */
  340.     emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
  341.     entropy->BE = 0;
  342.   }
  343. }
  344.  
  345.  
  346. /*
  347.  * Emit a restart marker & resynchronize predictions.
  348.  */
  349.  
  350. LOCAL(void)
  351. emit_restart (phuff_entropy_ptr entropy, int restart_num)
  352. {
  353.   int ci;
  354.  
  355.   emit_eobrun(entropy);
  356.  
  357.   if (! entropy->gather_statistics) {
  358.     flush_bits(entropy);
  359.     emit_byte(entropy, 0xFF);
  360.     emit_byte(entropy, JPEG_RST0 + restart_num);
  361.   }
  362.  
  363.   if (entropy->cinfo->Ss == 0) {
  364.     /* Re-initialize DC predictions to 0 */
  365.     for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
  366.       entropy->last_dc_val[ci] = 0;
  367.   } else {
  368.     /* Re-initialize all AC-related fields to 0 */
  369.     entropy->EOBRUN = 0;
  370.     entropy->BE = 0;
  371.   }
  372. }
  373.  
  374.  
  375. /*
  376.  * MCU encoding for DC initial scan (either spectral selection,
  377.  * or first pass of successive approximation).
  378.  */
  379.  
  380. METHODDEF(boolean)
  381. encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
  382. {
  383.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  384.   register int temp, temp2;
  385.   register int nbits;
  386.   int blkn, ci;
  387.   int Al = cinfo->Al;
  388.   JBLOCKROW block;
  389.   jpeg_component_info * compptr;
  390.   ISHIFT_TEMPS
  391.  
  392.   entropy->next_output_byte = cinfo->dest->next_output_byte;
  393.   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
  394.  
  395.   /* Emit restart marker if needed */
  396.   if (cinfo->restart_interval)
  397.     if (entropy->restarts_to_go == 0)
  398.       emit_restart(entropy, entropy->next_restart_num);
  399.  
  400.   /* Encode the MCU data blocks */
  401.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  402.     block = MCU_data[blkn];
  403.     ci = cinfo->MCU_membership[blkn];
  404.     compptr = cinfo->cur_comp_info[ci];
  405.  
  406.     /* Compute the DC value after the required point transform by Al.
  407.      * This is simply an arithmetic right shift.
  408.      */
  409.     temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
  410.  
  411.     /* DC differences are figured on the point-transformed values. */
  412.     temp = temp2 - entropy->last_dc_val[ci];
  413.     entropy->last_dc_val[ci] = temp2;
  414.  
  415.     /* Encode the DC coefficient difference per section G.1.2.1 */
  416.     temp2 = temp;
  417.     if (temp < 0) {
  418.       temp = -temp;        /* temp is abs value of input */
  419.       /* For a negative input, want temp2 = bitwise complement of abs(input) */
  420.       /* This code assumes we are on a two's complement machine */
  421.       temp2--;
  422.     }
  423.     
  424.     /* Find the number of bits needed for the magnitude of the coefficient */
  425.     nbits = 0;
  426.     while (temp) {
  427.       nbits++;
  428.       temp >>= 1;
  429.     }
  430.     
  431.     /* Count/emit the Huffman-coded symbol for the number of bits */
  432.     emit_symbol(entropy, compptr->dc_tbl_no, nbits);
  433.     
  434.     /* Emit that number of bits of the value, if positive, */
  435.     /* or the complement of its magnitude, if negative. */
  436.     if (nbits)            /* emit_bits rejects calls with size 0 */
  437.       emit_bits(entropy, (unsigned int) temp2, nbits);
  438.   }
  439.  
  440.   cinfo->dest->next_output_byte = entropy->next_output_byte;
  441.   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
  442.  
  443.   /* Update restart-interval state too */
  444.   if (cinfo->restart_interval) {
  445.     if (entropy->restarts_to_go == 0) {
  446.       entropy->restarts_to_go = cinfo->restart_interval;
  447.       entropy->next_restart_num++;
  448.       entropy->next_restart_num &= 7;
  449.     }
  450.     entropy->restarts_to_go--;
  451.   }
  452.  
  453.   return TRUE;
  454. }
  455.  
  456.  
  457. /*
  458.  * MCU encoding for AC initial scan (either spectral selection,
  459.  * or first pass of successive approximation).
  460.  */
  461.  
  462. METHODDEF(boolean)
  463. encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
  464. {
  465.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  466.   register int temp, temp2;
  467.   register int nbits;
  468.   register int r, k;
  469.   int Se = cinfo->Se;
  470.   int Al = cinfo->Al;
  471.   JBLOCKROW block;
  472.  
  473.   entropy->next_output_byte = cinfo->dest->next_output_byte;
  474.   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
  475.  
  476.   /* Emit restart marker if needed */
  477.   if (cinfo->restart_interval)
  478.     if (entropy->restarts_to_go == 0)
  479.       emit_restart(entropy, entropy->next_restart_num);
  480.  
  481.   /* Encode the MCU data block */
  482.   block = MCU_data[0];
  483.  
  484.   /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
  485.   
  486.   r = 0;            /* r = run length of zeros */
  487.    
  488.   for (k = cinfo->Ss; k <= Se; k++) {
  489.     if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
  490.       r++;
  491.       continue;
  492.     }
  493.     /* We must apply the point transform by Al.  For AC coefficients this
  494.      * is an integer division with rounding towards 0.  To do this portably
  495.      * in C, we shift after obtaining the absolute value; so the code is
  496.      * interwoven with finding the abs value (temp) and output bits (temp2).
  497.      */
  498.     if (temp < 0) {
  499.       temp = -temp;        /* temp is abs value of input */
  500.       temp >>= Al;        /* apply the point transform */
  501.       /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
  502.       temp2 = ~temp;
  503.     } else {
  504.       temp >>= Al;        /* apply the point transform */
  505.       temp2 = temp;
  506.     }
  507.     /* Watch out for case that nonzero coef is zero after point transform */
  508.     if (temp == 0) {
  509.       r++;
  510.       continue;
  511.     }
  512.  
  513.     /* Emit any pending EOBRUN */
  514.     if (entropy->EOBRUN > 0)
  515.       emit_eobrun(entropy);
  516.     /* if run length > 15, must emit special run-length-16 codes (0xF0) */
  517.     while (r > 15) {
  518.       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
  519.       r -= 16;
  520.     }
  521.  
  522.     /* Find the number of bits needed for the magnitude of the coefficient */
  523.     nbits = 1;            /* there must be at least one 1 bit */
  524.     while ((temp >>= 1))
  525.       nbits++;
  526.  
  527.     /* Count/emit Huffman symbol for run length / number of bits */
  528.     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
  529.  
  530.     /* Emit that number of bits of the value, if positive, */
  531.     /* or the complement of its magnitude, if negative. */
  532.     emit_bits(entropy, (unsigned int) temp2, nbits);
  533.  
  534.     r = 0;            /* reset zero run length */
  535.   }
  536.  
  537.   if (r > 0) {            /* If there are trailing zeroes, */
  538.     entropy->EOBRUN++;        /* count an EOB */
  539.     if (entropy->EOBRUN == 0x7FFF)
  540.       emit_eobrun(entropy);    /* force it out to avoid overflow */
  541.   }
  542.  
  543.   cinfo->dest->next_output_byte = entropy->next_output_byte;
  544.   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
  545.  
  546.   /* Update restart-interval state too */
  547.   if (cinfo->restart_interval) {
  548.     if (entropy->restarts_to_go == 0) {
  549.       entropy->restarts_to_go = cinfo->restart_interval;
  550.       entropy->next_restart_num++;
  551.       entropy->next_restart_num &= 7;
  552.     }
  553.     entropy->restarts_to_go--;
  554.   }
  555.  
  556.   return TRUE;
  557. }
  558.  
  559.  
  560. /*
  561.  * MCU encoding for DC successive approximation refinement scan.
  562.  * Note: we assume such scans can be multi-component, although the spec
  563.  * is not very clear on the point.
  564.  */
  565.  
  566. METHODDEF(boolean)
  567. encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
  568. {
  569.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  570.   register int temp;
  571.   int blkn;
  572.   int Al = cinfo->Al;
  573.   JBLOCKROW block;
  574.  
  575.   entropy->next_output_byte = cinfo->dest->next_output_byte;
  576.   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
  577.  
  578.   /* Emit restart marker if needed */
  579.   if (cinfo->restart_interval)
  580.     if (entropy->restarts_to_go == 0)
  581.       emit_restart(entropy, entropy->next_restart_num);
  582.  
  583.   /* Encode the MCU data blocks */
  584.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  585.     block = MCU_data[blkn];
  586.  
  587.     /* We simply emit the Al'th bit of the DC coefficient value. */
  588.     temp = (*block)[0];
  589.     emit_bits(entropy, (unsigned int) (temp >> Al), 1);
  590.   }
  591.  
  592.   cinfo->dest->next_output_byte = entropy->next_output_byte;
  593.   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
  594.  
  595.   /* Update restart-interval state too */
  596.   if (cinfo->restart_interval) {
  597.     if (entropy->restarts_to_go == 0) {
  598.       entropy->restarts_to_go = cinfo->restart_interval;
  599.       entropy->next_restart_num++;
  600.       entropy->next_restart_num &= 7;
  601.     }
  602.     entropy->restarts_to_go--;
  603.   }
  604.  
  605.   return TRUE;
  606. }
  607.  
  608.  
  609. /*
  610.  * MCU encoding for AC successive approximation refinement scan.
  611.  */
  612.  
  613. METHODDEF(boolean)
  614. encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
  615. {
  616.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  617.   register int temp;
  618.   register int r, k;
  619.   int EOB;
  620.   char *BR_buffer;
  621.   unsigned int BR;
  622.   int Se = cinfo->Se;
  623.   int Al = cinfo->Al;
  624.   JBLOCKROW block;
  625.   int absvalues[DCTSIZE2];
  626.  
  627.   entropy->next_output_byte = cinfo->dest->next_output_byte;
  628.   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
  629.  
  630.   /* Emit restart marker if needed */
  631.   if (cinfo->restart_interval)
  632.     if (entropy->restarts_to_go == 0)
  633.       emit_restart(entropy, entropy->next_restart_num);
  634.  
  635.   /* Encode the MCU data block */
  636.   block = MCU_data[0];
  637.  
  638.   /* It is convenient to make a pre-pass to determine the transformed
  639.    * coefficients' absolute values and the EOB position.
  640.    */
  641.   EOB = 0;
  642.   for (k = cinfo->Ss; k <= Se; k++) {
  643.     temp = (*block)[jpeg_natural_order[k]];
  644.     /* We must apply the point transform by Al.  For AC coefficients this
  645.      * is an integer division with rounding towards 0.  To do this portably
  646.      * in C, we shift after obtaining the absolute value.
  647.      */
  648.     if (temp < 0)
  649.       temp = -temp;        /* temp is abs value of input */
  650.     temp >>= Al;        /* apply the point transform */
  651.     absvalues[k] = temp;    /* save abs value for main pass */
  652.     if (temp == 1)
  653.       EOB = k;            /* EOB = index of last newly-nonzero coef */
  654.   }
  655.  
  656.   /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
  657.   
  658.   r = 0;            /* r = run length of zeros */
  659.   BR = 0;            /* BR = count of buffered bits added now */
  660.   BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
  661.  
  662.   for (k = cinfo->Ss; k <= Se; k++) {
  663.     if ((temp = absvalues[k]) == 0) {
  664.       r++;
  665.       continue;
  666.     }
  667.  
  668.     /* Emit any required ZRLs, but not if they can be folded into EOB */
  669.     while (r > 15 && k <= EOB) {
  670.       /* emit any pending EOBRUN and the BE correction bits */
  671.       emit_eobrun(entropy);
  672.       /* Emit ZRL */
  673.       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
  674.       r -= 16;
  675.       /* Emit buffered correction bits that must be associated with ZRL */
  676.       emit_buffered_bits(entropy, BR_buffer, BR);
  677.       BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
  678.       BR = 0;
  679.     }
  680.  
  681.     /* If the coef was previously nonzero, it only needs a correction bit.
  682.      * NOTE: a straight translation of the spec's figure G.7 would suggest
  683.      * that we also need to test r > 15.  But if r > 15, we can only get here
  684.      * if k > EOB, which implies that this coefficient is not 1.
  685.      */
  686.     if (temp > 1) {
  687.       /* The correction bit is the next bit of the absolute value. */
  688.       BR_buffer[BR++] = (char) (temp & 1);
  689.       continue;
  690.     }
  691.  
  692.     /* Emit any pending EOBRUN and the BE correction bits */
  693.     emit_eobrun(entropy);
  694.  
  695.     /* Count/emit Huffman symbol for run length / number of bits */
  696.     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
  697.  
  698.     /* Emit output bit for newly-nonzero coef */
  699.     temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
  700.     emit_bits(entropy, (unsigned int) temp, 1);
  701.  
  702.     /* Emit buffered correction bits that must be associated with this code */
  703.     emit_buffered_bits(entropy, BR_buffer, BR);
  704.     BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
  705.     BR = 0;
  706.     r = 0;            /* reset zero run length */
  707.   }
  708.  
  709.   if (r > 0 || BR > 0) {    /* If there are trailing zeroes, */
  710.     entropy->EOBRUN++;        /* count an EOB */
  711.     entropy->BE += BR;        /* concat my correction bits to older ones */
  712.     /* We force out the EOB if we risk either:
  713.      * 1. overflow of the EOB counter;
  714.      * 2. overflow of the correction bit buffer during the next MCU.
  715.      */
  716.     if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
  717.       emit_eobrun(entropy);
  718.   }
  719.  
  720.   cinfo->dest->next_output_byte = entropy->next_output_byte;
  721.   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
  722.  
  723.   /* Update restart-interval state too */
  724.   if (cinfo->restart_interval) {
  725.     if (entropy->restarts_to_go == 0) {
  726.       entropy->restarts_to_go = cinfo->restart_interval;
  727.       entropy->next_restart_num++;
  728.       entropy->next_restart_num &= 7;
  729.     }
  730.     entropy->restarts_to_go--;
  731.   }
  732.  
  733.   return TRUE;
  734. }
  735.  
  736.  
  737. /*
  738.  * Finish up at the end of a Huffman-compressed progressive scan.
  739.  */
  740.  
  741. METHODDEF(void)
  742. finish_pass_phuff (j_compress_ptr cinfo)
  743. {   
  744.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  745.  
  746.   entropy->next_output_byte = cinfo->dest->next_output_byte;
  747.   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
  748.  
  749.   /* Flush out any buffered data */
  750.   emit_eobrun(entropy);
  751.   flush_bits(entropy);
  752.  
  753.   cinfo->dest->next_output_byte = entropy->next_output_byte;
  754.   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
  755. }
  756.  
  757.  
  758. /*
  759.  * Finish up a statistics-gathering pass and create the new Huffman tables.
  760.  */
  761.  
  762. METHODDEF(void)
  763. finish_pass_gather_phuff (j_compress_ptr cinfo)
  764. {
  765.   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
  766.   boolean is_DC_band;
  767.   int ci, tbl;
  768.   jpeg_component_info * compptr;
  769.   JHUFF_TBL **htblptr;
  770.   boolean did[NUM_HUFF_TBLS];
  771.  
  772.   /* Flush out buffered data (all we care about is counting the EOB symbol) */
  773.   emit_eobrun(entropy);
  774.  
  775.   is_DC_band = (cinfo->Ss == 0);
  776.  
  777.   /* It's important not to apply jpeg_gen_optimal_table more than once
  778.    * per table, because it clobbers the input frequency counts!
  779.    */
  780.   MEMZERO(did, SIZEOF(did));
  781.  
  782.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  783.     compptr = cinfo->cur_comp_info[ci];
  784.     if (is_DC_band) {
  785.       if (cinfo->Ah != 0)    /* DC refinement needs no table */
  786.     continue;
  787.       tbl = compptr->dc_tbl_no;
  788.     } else {
  789.       tbl = compptr->ac_tbl_no;
  790.     }
  791.     if (! did[tbl]) {
  792.       if (is_DC_band)
  793.         htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
  794.       else
  795.         htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
  796.       if (*htblptr == NULL)
  797.         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
  798.       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
  799.       did[tbl] = TRUE;
  800.     }
  801.   }
  802. }
  803.  
  804.  
  805. /*
  806.  * Module initialization routine for progressive Huffman entropy encoding.
  807.  */
  808.  
  809. GLOBAL(void)
  810. jinit_phuff_encoder (j_compress_ptr cinfo)
  811. {
  812.   phuff_entropy_ptr entropy;
  813.   int i;
  814.  
  815.   entropy = (phuff_entropy_ptr)
  816.     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  817.                 SIZEOF(phuff_entropy_encoder));
  818.   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
  819.   entropy->pub.start_pass = start_pass_phuff;
  820.  
  821.   /* Mark tables unallocated */
  822.   for (i = 0; i < NUM_HUFF_TBLS; i++) {
  823.     entropy->derived_tbls[i] = NULL;
  824.     entropy->count_ptrs[i] = NULL;
  825.   }
  826.   entropy->bit_buffer = NULL;    /* needed only in AC refinement scan */
  827. }
  828.  
  829. #endif /* C_PROGRESSIVE_SUPPORTED */
  830.